/*
 * ReverseColussi.cpp
 *
 *  Created on: 22-08-2013
 *      Author: Krzychu
 */

#include "ReverseColussi.h"

#include "Config.h"

#include <stdio.h>
#include <string.h>

#define ASIZE 255

ReverseColussi::ReverseColussi()
{

}

ReverseColussi::~ReverseColussi()
{

}

std::string ReverseColussi::getName()
{
	return "Reverse Colussi";
}

void preRevColussi(std::string pattern, int* h, int** rcBc, int* rcGs)
{
	int a, i, j, k, q, r, s;
	int patternSize = pattern.size();

	int* hmin = new int[patternSize];
	int* kmin = new int[patternSize];
	int* link = new int[patternSize];
	int* locc = new int[ASIZE];
	int* rmin = new int[patternSize];

	/* Computation of link and locc */
	for (a = 0; a < ASIZE; ++a)
	{
		locc[a] = -1;
	}
	link[0] = -1;
	for (i = 0; i < patternSize - 1; ++i)
	{
		link[i + 1] = locc[pattern[i]];
		locc[pattern[i]] = i;
	}

	/* Computation of rcBc */
	for (a = 0; a < ASIZE; ++a)
	{
		for (s = 1; s <= patternSize; ++s)
		{
			i = locc[a];
			j = link[patternSize - s];
			while (i - j != s && j >= 0)
			{
				if (i - j > s)
				{
					i = link[i + 1];
				}
				else
				{
					j = link[j + 1];
				}
			}
			while (i - j > s)
			{
				i = link[i + 1];
			}
			rcBc[a][s] = patternSize - i - 1;
		}
	}

	/* Computation of hmin */
	k = 1;
	i = patternSize - 1;
	while (k <= patternSize)
	{
		while (i - k >= 0 && pattern[i - k] == pattern[i])
		{
			--i;
		}
		hmin[k] = i;
		q = k + 1;
		while (hmin[q - k] - (q - k) > i)
		{
			hmin[q] = hmin[q - k];
			++q;
		}
		i += (q - k);
		k = q;
		if (i == patternSize)
		{
			i = patternSize - 1;
		}
	}

	/* Computation of kmin */
	memset(kmin, 0, patternSize * sizeof(int));
	for (k = patternSize; k > 0; --k)
	{
		kmin[hmin[k]] = k;
	}

	/* Computation of rmin */
	for (i = patternSize - 1; i >= 0; --i)
	{
		if (hmin[i + 1] == i)
		{
			r = i + 1;
		}
		rmin[i] = r;
	}

	/* Computation of rcGs */
	i = 1;
	for (k = 1; k <= patternSize; ++k)
	{
		if (hmin[k] != patternSize - 1 && kmin[hmin[k]] == k)
		{
			h[i] = hmin[k];
			rcGs[i++] = k;
		}
	}
	i = patternSize - 1;
	for (j = patternSize - 2; j >= 0; --j)
	{
		if (kmin[j] == 0)
		{
			h[i] = j;
			rcGs[i--] = rmin[j];
		}
	}
	rcGs[patternSize] = rmin[0];
}

searchResult ReverseColussi::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();
	int* rcGs = new int[patternSize];
	int* h = new int[patternSize];

	int** rcBc = new int*[ASIZE];
	for (int i = 0; i < ASIZE; i++)
	{
		rcBc[i] = new int[patternSize];
	}

	/* Preprocessing */
	preRevColussi(pattern, h, rcBc, rcGs);

	/* Searching */
	int j = 0;
	int s = patternSize;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;
		while (j <= textSize - patternSize
				&& pattern[patternSize - 1] != text[j + patternSize - 1])
		{
			s = rcBc[text[j + patternSize - 1]][s];
			j += s;
		}
		int i;
		for (i = 1; i < patternSize && pattern[h[i]] == text[j + h[i]]; ++i)
			;
		if (i >= patternSize)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
		}
		s = rcGs[i];
		j += s;
	}

	return result;
}

